#include "node.h"

class Solution {
public:
    /**
     * @param head Node类 
     * @return Node类
     */
    Node* ReverseList(Node* head) {
        // return reverse(nullptr, head);
        return reverse(head);
    }


private:
    //! Version-1: left (reversed ) + right (unreversed)
    // Node* reverse(Node* prev, Node* curr) {
    //     // if (curr == nullptr) {
    //     //     return prev;             // 当curr为空时，prev就是新的头节点
    //     // }
    //     Node* next = curr->next;     // 保存下一个节点
    //     // curr->next = prev;           // 反转当前节点的next指针
    //     // return reverse(curr, next);  // 递归处理下一个节点
    //     Node* new_head = reverse(next);
    // }

    //! Version-2: head + unreversed
    Node* reverse(Node* head) {
        if (head->next == nullptr || head == nullptr) {
            return head;
        }

        Node* next     = head->next;     
        Node* new_head = reverse(next);
        next->next     = head;
        head->next     = nullptr;  
        return new_head;
    }

    //! Version3: 使用循环，不使用递归
    // Node* reverse(Node* head) {
    //     Node* prev = nullptr;  // 前一个节点，初始化为 nullptr
    //     Node* curr = head;     // 当前节点，初始化为头节点
    //     Node* next = nullptr;  // 下一个节点，初始化为 nullptr
    
    //     while (curr != nullptr) {
    //         next = curr->next;  // 保存下一个节点
    //         curr->next = prev;  // 反转当前节点的 next 指针
    //         prev = curr;        // 移动 prev 到当前节点
    //         curr = next;        // 移动 curr 到下一个节点
    //     }
    
    //     return prev;  // 返回新的头节点
    // }
};